package baseclass.k_array;

/**
 * @date 2020/3/4 20:27
 */
public class Code04_HowMuchWater {
    public static int getMaxWater3(int[] height) {
        if(height == null ||height.length <= 2) return 0;
        int res = 0;
        int lMax = height[0];
        int rMax = height[height.length-1];
        int left = 1;
        int right = height.length - 2;
        while (left <= right){
            //右侧最大值更大，那么更新左侧最大值，左侧++。因为水取决于最大值中较小者
            if(rMax > lMax){
                res += Math.max(lMax - height[left], 0);
                lMax = Math.max(lMax,height[left++]);
            }else {
                res += (Math.max(rMax - height[right], 0));
                rMax = Math.max(rMax,height[right--]);
            }
        }
        return res;
    }
    public static int getMaxWater1(int[] arr) {
        int res = 0;
        //从1到N-2遍历即可
        int delta = 0;
        for (int i = 1; i < arr.length - 1; i++) {
            delta = Math.min(getMax(arr, 0, i), getMax(arr, i + 1, arr.length - 1));
            res += delta - arr[i];
        }
        return res;
    }

    public static int getMax(int[] arr, int begin, int end) {
        int max = Integer.MIN_VALUE;
        for (int i = begin; i <= end; i++) {
            max = Math.max(max, arr[i]);
        }
        return max;
    }

    public static int getMaxWater2(int[] arr) {
        int[] leftMax = new int[arr.length];
        int[] rightMax = new int[arr.length];
        leftMax[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], arr[i]);
        }
        rightMax[arr.length - 1] = arr[arr.length - 1];
        for (int i = arr.length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], arr[i]);
        }
        int res = 0;
        int delta = 0;
        for (int i = 1; i < arr.length - 1; i++) {
            delta = Math.min(leftMax[i-1], rightMax[i+1]);
            res += delta - arr[i];
        }
        return res;
    }

    public static void main(String[] args) {
        int []arr = {3,1,2,4};
        System.out.println(getMaxWater3(arr));
        System.out.println(getMaxWater2(arr));
    }
}
